import collections
from typing import List


class Solution:
    def chaseGame(self, edges: List[List[int]], start1: int, start2: int) -> int:
        # 结点数
        n = len(edges)

        # 生成无向图中边的邻接列表结构
        graph = collections.defaultdict(set)
        for edge in edges:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])

        # ---------- 寻找被追者所在小径与无向图中唯一的一个环的交点、环的周长、被追者到交点的距离 ----------
        # 无向图：N个点、N条边、不存在重复边、不存在无法到达的点 -> 无向图中只有唯一的一个环
        # 如果被追者当前正在环上则返回被追者当前位置

        def dfs1(last, now, step):
            """深度优先搜索寻找被追者所在小径与无向图中唯一的一个环的交点"""
            visited1[now] = step
            for nxt in graph[now]:
                if nxt == last:
                    continue
                if nxt in visited1:
                    return nxt, step - visited1[nxt] + 1, visited1[nxt]
                else:
                    res = dfs1(now, nxt, step + 1)
                    if res is not None:
                        return res
            return None

        visited1 = {}
        cross, circle_length, distance2 = dfs1(None, start2, 0)

        # print("被追者所在小径与无向图中唯一的一个环的交点:", cross, "环的周长:", circle_length)
        # print("被追者距离交点的距离:", distance2)

        # ---------- 计算追逐者能否追上被追者 ----------
        # 如果环的周长小于4，那么被追者一定会被追上
        # 如果被追者到达交点的距离大于等于(追逐者到达交点的距离+1)，那么被追者一定会被追上（因为追逐者先手）
        # 如果被追者距离追逐者的距离等于1，那么被追者会在第1回合被追上（因为追逐者先手）

        def bfs1(start, distance_lst):
            """广度优先搜索距离各个点追逐者的最近距离"""
            now_distance = 0
            visited = {start}
            queue = collections.deque([start])
            while queue:
                for _ in range(len(queue)):
                    node = queue.popleft()
                    distance_lst[node] = now_distance
                    for nxt in graph[node]:
                        if nxt not in visited:
                            queue.append(nxt)
                            visited.add(nxt)
                now_distance += 1

        # 计算追逐者到达各个点的距离
        distance1_lst = {}
        bfs1(start1, distance1_lst)
        # print("追逐者距离交点的距离:", distance1_lst[cross])

        # 如果被追者距离追逐者的距离等于1，那么被追者会在第1回合被追上
        if distance1_lst[start2] == 1:
            return 1

        # 计算追逐者能否追上被追者
        if circle_length >= 4 and distance2 + 1 < distance1_lst[cross]:
            return -1

        # ---------- 计算追逐者追进被追者所在小巷后被追者能够躲藏的最大距离 ----------
        # 被追者应尽可能在追逐者到来前，找到最深的小巷，并躲藏到小巷的最后
        # 因此被追者在尝试移动到最深的小巷时，随时需要判断当前位置是否可能被追逐者堵住

        def bfs2(start, distance_lst):
            """广度优先搜索距离各个点被追者的最近距离"""
            now_distance = 0
            visited = {start}
            queue = collections.deque([start])
            while queue:
                for _ in range(len(queue)):
                    node = queue.popleft()
                    distance_lst[node] = now_distance
                    for nxt in graph[node]:
                        if now_distance + 2 < distance1_lst[nxt]:  # 当前点不会被追逐者堵住（追逐者先手）
                            if nxt not in visited:
                                queue.append(nxt)
                                visited.add(nxt)
                now_distance += 1

        # 计算被追者到达各个点的距离
        distance2_lst = {}
        bfs2(start2, distance2_lst)
        # print(distance2_lst)

        # 寻找被追者距离更近的，追逐者需要用的最远距离
        ans = 0
        for i in distance2_lst:
            if distance2_lst[i] < distance1_lst[i]:
                ans = max(ans, distance1_lst[i])
        return ans


if __name__ == "__main__":
    # 3
    print(Solution().chaseGame(edges=[[1, 2], [2, 3], [3, 4], [4, 1], [2, 5], [5, 6]], start1=3, start2=5))

    # -1
    print(Solution().chaseGame(edges=[[1, 2], [2, 3], [3, 4], [4, 1]], start1=1, start2=3))

    # 测试用例50 : 1
    print(Solution().chaseGame(edges=[[1, 2], [2, 3], [3, 4], [4, 1]], start1=1, start2=2))

    # 测试用例53 : 3
    print(Solution().chaseGame(edges=[[1, 2], [2, 3], [3, 1], [3, 6], [2, 4], [4, 5], [5, 8], [4, 7]],
                               start1=8, start2=7))
